package com.dsaa.dfs;

import org.redisson.api.StreamMessageId;

import java.util.ArrayList;
import java.util.Arrays;
import java.util.List;
import java.util.stream.Collectors;
import java.util.stream.Stream;

class Solution {
    
    List<List<Integer>> ans = new ArrayList<>();

    public List<List<Integer>> permuteUnique(int[] nums) {
        Arrays.sort(nums);

        dfs(nums, 0, nums.length -1);

        return ans;
    }

    void dfs(int[] nums, int left, int right) {
        if (left == right) {
            List<Integer> list = new ArrayList<>();
            for (int num : nums) { list.add(num); }
            ans.add(list);
        } else {
            for (int i = left; i <= right; i++) {
                if (i != left && nums[left] == nums[i]) {
                    continue;
                }
                int temp = nums[left];
                nums[left] = nums[i];
                nums[i] = temp;

                dfs(nums, left + 1, right);
            }
        }
    }
}


